{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<center><h1> Directed graphical models (Bayesian Networks) </h1></center>\n",
    "\n",
    "# 1. Basic idea\n",
    "The directed graphical models are intented to represent the joint distribution $p(\\vec{x}|\\theta)$,especially for high dimension data.By the **chain rule** of probability,we can always represent a joint distribution as follows\n",
    "$$\n",
    "p(x_{1:V})=p(x_1)p(x_2|x_1)p(x_3|x_1,x_2) \\dots p(x_V|x_{V-1},\\ldots,x_1)\n",
    "$$\n",
    "The problem is that when the $V$ is large, the distribution $p(x_V|x_{V-1},\\ldots,x_1)$ will be very complicate. The reason is that we have not make any assumptions on the dependence relationship between the data.\n",
    "\n",
    "The key to efficiently representing large joint distributions is to make some assumptions about the **conditional independence (CI)**. This is the magic of the directed graphical models.\n",
    "$$\n",
    "X \\perp Y\\,|\\,Z \\longleftrightarrow p(X,Y\\,|\\,Z)=p(X\\,|\\,Z)p(Y\\,|\\,Z) \\longleftrightarrow p(X\\,|\\,Y,Z)=p(X\\,|\\,Z)\n",
    "$$\n",
    "\n",
    "A graphical model(GM) is a way to represent a joint distribution by making **CI** assumptions. The nodes in the graph represent random variables, and the (lack of)edges represent **CI** assumptions. A **directed graphical model(DGM)** is a GM whose graph is a **directed acyclic graph(DAG)**. These are more commonly known as **Bayesian networks**.\n",
    "\n",
    "The key property of **DAG** is that the nodes can be ordered such that parents come before children using **topological ordering**.Given such an order, we define the **ordered Markov property** to be the assumption that  a node only depends on its immediate parents, not on all predecessors in the ordering\n",
    "\n",
    "$$\n",
    "x_s \\perp x_{pred(s)\\backslash pa(s)}  | x_{pa(s)}\n",
    "$$\n",
    "\n",
    "where $pa(s)$ are the parents of node s, and $pred(s)$ are the predecessors of node $s$ in the topological ordering. The joint distribution defined by a graph is given by the product, over all of the nodes of the graph, of a conditional distribution for each node conditioned on the variables corresponding to the parents of that node in the graph. Thus, for a graph with $K$ nodes, the joint distribution is given by\n",
    "$$\n",
    "p(x_{1:K})=\\prod_{k=1}^K p(x_k|pa_k)\n",
    "$$\n",
    "<img src=\"imgs/1.png\" alt=\"drawing\" width=\"250\"/>\n",
    "The DAG above encodes the following joint distribution\n",
    "\\begin{align}\n",
    "p(x_1,x_2,x_3,x_4,x_5) &=p(x_1)p(x_2|x_1)p(x_3|x_1)p(x_4|x_2,x_3)p(x_5|x_3) \\\\\n",
    "\\end{align}\n",
    "\n",
    "# 2. Some examples\n",
    "## 2.1 Polynomial regression\n",
    "Consider the bayesian polynomial regression model with training dataset $D=\\left\\{(x_i,y_i)\\right\\}_{i=1}^N$.\n",
    "\\begin{align}\n",
    "\\vec{t} &=\\left(1,x,x^2,\\ldots,x^K\\right) \\\\\n",
    "y&=\\mathcal{N}(\\vec{t}^T\\vec{w},\\sigma^2) \\\\\n",
    "\\vec{w} &\\sim \\mathcal{N}(\\mathbf{0},\\frac{1}{\\alpha} \\mathbf{I})\n",
    "\\end{align}\n",
    "The random variables in this model are the vector of polynomial coefficients $\\vec{w}$ and the observed data $Y=\\left(y_1,y_2,\\ldots,y_N\\right)$. The noise variance $\\sigma^2$, the hyperparameter $\\alpha$ representing the precision of the Gaussian prior over $\\vec{w}$  and the input data $X=\\left(x_1,x_2,\\ldots x_N\\right)$ are **parameters** of the model rather than random variables. In a graphical model, we will denote **observed variables** by shading the corresponding nodes.The other non-observed variable is called **latent variable**.\n",
    "<img src=\"imgs/2.png\" alt=\"drawing\" width=\"250\"/>\n",
    "Having observed the values $\\left\\{y_1,y_2,\\ldots,y_N\\right\\}$ we can, if desired, evaluate the posterior   distribution of the polynomial coefficients $\\vec{w}$ using bayes law as follows\n",
    "$$\n",
    "p(\\vec{w}|Y) \\propto p(w) \\prod_{n=1}^N p(y_n|\\vec{w})\n",
    "$$\n",
    "In general, model parameters such as $\\vec{w}$ are of little direct interest in themselves,because our ultimate goal is to make predictions for new input values. For predictions, the graphical model that describles this problem is shown below.\n",
    "<img src=\"imgs/3.png\" alt=\"drawing\" width=\"250\"/>\n",
    "We can make predictions as follows\n",
    "\\begin{align}\n",
    "p(y_{new}|Y) &=\\int p(y_{new},\\vec{w}|Y)d\\vec{w} \\\\\n",
    "             &=\\int p(y_{new}|\\vec{w},Y)p(\\vec{w}|Y)d\\vec{w} \\\\\n",
    "             &=\\int p(y_{new}|\\vec{w})p(\\vec{w}|Y)d\\vec{w} \\\\\n",
    "\\end{align}\n",
    "**The secret is that condition on the observed variables and margin the irrelevant latent variables .**\n",
    "\n",
    "We can also represent $\\sigma^2$ and $\\alpha$ as random variable, which lead to more complex models.\n",
    "\\begin{align}\n",
    "\\sigma^2 &\\sim Gamma(\\alpha_0,\\beta_0) \\\\\n",
    "\\alpha &\\sim Gamma(\\alpha_1,\\beta_1) \\\\\n",
    "\\end{align}\n",
    "<img src=\"imgs/4.png\" alt=\"drawing\" width=\"250\"/>\n",
    "We can get even more complex models by making $x$ being random variable as follows.\n",
    "<img src=\"imgs/5.png\" alt=\"drawing\" width=\"250\"/>\n",
    "Therefore, there are no distinct difference between parameters and random variables in DGMs. More random variables, more complex the model.\n",
    "## 2.2 Directed Gaussian graphical models\n",
    "Consider a DGM where all the variable are real-valued and all the conditional distribution have the following form\n",
    "$$\n",
    "p(x_t|\\vec{x_{pa(t)}})=\\mathcal{N}(x_t|\\mu_t+\\vec{w}_t^T\\vec{x_{pa(t)}},\\sigma_t^2)\n",
    "$$\n",
    "This is called a linear Gaussian distribution.Multiplying all these conditional distribution together results in a large joint Gaussian distribution. Several widely used techniques are examples of linear-Gaussian models, such as probabilistic principal component analysis, factor analysis and linear dynamic systems.\n",
    "# 3. D-separation\n",
    "We now give a general statement of the CI property for directed graphs.Consider a general directed graph in which A, B, and C are arbitrary sets of nodes.We wish to ascertain whether a particular conditional\n",
    "independence statement $ A \\perp B\\,|\\,C$ is implied by a given directed acyclic graph.To do so, we consider all possible paths from any node in $A$ to any node in $B$. Any such path is said to be blocked if it includes a node such that either\n",
    "* the arrows on the path meet either head-to-tail or tail-to-tail at the node, and the node is in the set $C$.\n",
    "* the arrows meet head-to-head at the node, and neither the node, nor any of its descendants, is in the set $C$.\n",
    "\n",
    "If all paths are blocked, then $A$ is said to be d-separated from $B$ by $C$. For example, the graph below, the path from $a$ to $b$ is $a \\rightarrow e \\rightarrow f \\rightarrow b$. The path is blocked by $e$ because it's a head-head node and  neither the node, nor any of its descendants are observed.  The path is blocked by $f$ because it's a tail-tail node and the node is observed. So $a$ and $b$ is independent condition on the observed variables.\n",
    "<img src=\"imgs/6.png\" alt=\"drawing\" width=\"250\"/>\n",
    "Another example, the path from $a$ to $b$ is $a \\rightarrow e \\rightarrow f \\rightarrow b$. The path is not blocked by  $f$ because it's a tail-tail node and not observed. The path is not blocked by $e$ because it's a head-head node and its child is observed. So $a$ and $b$ is not independent condition on the observed variables.  \n",
    "<img src=\"imgs/7.png\" alt=\"drawing\" width=\"250\"/>\n",
    "\n",
    "# 4. Inference\n",
    "Suppose we have a set of correlated random variables with joint distribution $p(x_{1:V|\\theta})$ (In this section,we are assuming the parameters $\\theta$ of the model are known). Let us partition this vector into the **visible variables** $x_v$, which are observed, and the **hidden variables** $x_h$, which are unobserved. Inference refers to computing the posterior distribution of the unknowns given the knowns\n",
    "\\begin{align}\n",
    "p(x_h|x_v,\\theta) &=\\frac{p(x_v,x_h|\\theta)}{p(x_v|\\theta)} \\\\\n",
    "                  &=\\frac{p(x_v,x_h|\\theta)}{\\sum_{x_h'}p(x_v,x_h',\\theta)} \\\\\n",
    "\\end{align}\n",
    "\n",
    "In the hidden variables, only some of them are of interest to us, which denoted as $x_q$. We can compute what we are interested in by **marginalizing out** the rest **nuisance variables** $x_n$.\n",
    "$$\n",
    "p(x_q|x_v,\\theta)=\\sum_{x_n} p(x_h|x_v,\\theta)\n",
    "$$\n",
    "\n",
    "# 5. Learning\n",
    "In inference, we assume that the parameter $\\theta$ is known to us. But actually, we need to computing a MAP estimate of the parameters given training data.\n",
    "$$\n",
    "\\hat{\\theta}=\\underset{\\theta}{argmax} \\sum_{i=1}^N log\\,p(x_{i,v}|\\theta)+log\\, p(\\theta)\n",
    "$$\n",
    "where $x_{i,v}$ are visible variables in train data sample i. If we have a uniform prior, $p(\\theta) \\propto 1$, this reduces to the MLE.\n",
    "\n",
    "### Learning form complete data\n",
    "If all the variables are fully observed in each case, so there is no missing data and there are no hidden variables, we say the data is **complete**. For a DGM with complete data, the likelihood is given by\n",
    "\\begin{align}\n",
    "p(D|\\theta) &=\\prod_{i=1}^N p(x_i|\\theta) \\\\\n",
    "            &=\\prod_{i=1}^N \\prod_{t=1}^V p(x_{it}|x_{i,pa(t)},\\theta_t) \\\\\n",
    "            &=\\prod_{t=1}^V p(D_t|\\theta_t)\n",
    "\\end{align}\n",
    "where $D_t$ is the data associated with the node $t$ and its parents. This is a product of terms, which means likelihood **decomposes** according to the graph structure.\n",
    "\n",
    "Now suppose that the prior factorizes as well\n",
    "$$\n",
    "p(\\theta)=\\prod_{t=1}^V p(\\theta_t)\n",
    "$$\n",
    "Then clearly the posterior also factorizes\n",
    "\\begin{align}\n",
    "p(\\theta|D) &\\propto p(\\theta)p(D|\\theta) \\\\\n",
    "            &=\\prod_{t=1}^V p(\\theta_t)p(D_t|\\theta_t) \n",
    "\\end{align}\n",
    "This means we can compute the posterior of each conditional distribution independently, just as the Naive Bayes classification case.\n",
    "\n",
    "### Learning with missing and/or latent variables\n",
    "If we have missing data and/or hidden variables, the likelihood no longer factorizes, and the troubles come. We will discuss in the following chapters."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [default]",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
